#include "Graph.h"
#include <iostream>
#include<string.h>
ECOperateResult DynamicDirectGraph::Insert(int start, int go, int w)
{
	if (start > Size||go>Size)
		return ECOperateResult::Unknown;
	else
	{
		ItemTable[start].emplace_back(w, go);
		return ECOperateResult::Success;
	}
}
ECOperateResult DynamicDirectGraph::Dijkstra(int start)
{
	Dis[start] = 0;
	DoDijkstra.emplace(0, start);
	while (!DoDijkstra.empty())
	{
		DirectGraphItem Temp = DoDijkstra.top();
		DoDijkstra.pop();
		int Start = Temp.n;
		int _Size = ItemTable[Start].size();
		if (Check[Start]) continue;
		Check[Start] = 1;
		for (int j = 0; j < _Size; j++)
		{
			int Next = ItemTable[Start][j].n;//Start代表出发点，j代表从Start出发的第j个终点，n代表终点编号
			if (Dis[Next] > Dis[Start] + ItemTable[Start][j].w)
			{
				Dis[Next] = Dis[Start] + ItemTable[Start][j].w;
				if (!Check[Next])    //如果没有被访问过，入队
				{
					DoDijkstra.emplace(Dis[Next], Next);
				}
			}
		}
	}
	for (int i = 1; i <= Size; i++) cout << Dis[i] << " ";
	return ECOperateResult::Success;
}
void DynamicDirectGraph::DFS(int Node,int flag)  //查询连通关系
{
    if(!flag) memset(Vis,0,Size*sizeof(bool));
    for(int i=0;i<ItemTable[Node].size();i++)
    {
        if(Vis[ItemTable[Node][i].n]) continue;
        Vis[ItemTable[Node][i].n]=true;
        std::cout<<ItemTable[Node][i].n<<"  ";
        DFS(ItemTable[Node][i].n,1);
    }
}


ECOperateResult DynamicUnDirectGraph::Insert(int start, int go, int w)
{
	if (start > Size || go > Size)
		return ECOperateResult::Unknown;
	else
	{
		Item[start].emplace_back(w, go);
		Item[go].emplace_back(w, start);
		return ECOperateResult::Success;
	}
}
ECOperateResult DynamicUnDirectGraph::Prim()
{
	DoPrim.emplace(0,1);
	Dis[1] = 0;
	while (!DoPrim.empty())
	{
		int Start = DoPrim.top().n;
		DoPrim.pop();
		if (Check[Start]) continue;
		Check[Start] = true;
		Ans += Dis[Start];
		//for (auto [Next,Value] : Item[Start])   范围for循环遍历容器元素 未实现
		int j = Item[Start].size();
		for (int i = 0; i < j; i++)
		{
			int Next = Item[Start][i].n;
			int Value= Item[Start][i].w;
			if (Dis[Next]>Value && !Check[Next])
			{
				Dis[Next] = Value;
				DoPrim.emplace(Dis[Next], Next);
			}
		}
	}
	for (int i = 0; i < Size; i++)  //
	{
		if (Dis[i] == std::numeric_limits<uint32_t>::max())   //图并不连通
			return ECOperateResult::GraphNotPass;
	}
	return ECOperateResult::Success;
}